//给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 
//
// 返回 s 所有可能的分割方案。 
//
// 示例: 
//
// 输入: "aab"
//输出:
//[
//  ["aa","b"],
//  ["a","a","b"]
//] 
// Related Topics 回溯算法 
// 👍 356 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

//Java：分割回文串
public class P131PalindromePartitioning {

    /**
     *
     * 思路：回溯算法，先 [0,1] 分割，然后回溯[0,2] 分割，以此类推
     *
     * 执行用时： 10 ms , 在所有 Java 提交中击败了 13.92% 的用户 内存消耗： 40.9 MB , 在所有 Java 提交中击败了 22.54% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        List<List<String>> list = new ArrayList<>();

        public List<List<String>> partition(String s) {
            if (s.length() != 0) {
                dfs(0, 0, s, new Stack<>());
            }
            return list;
        }

        // a b b a e
        // i 1    s5
        private void dfs(int left, int right, String s, Stack<String> stack) {
            if (left < right) {
                boolean flag = isR(s.substring(left, right));
                if (!flag) {
                    return;
                }

                if (right == s.length()) {
                    list.add(new ArrayList<>(stack));
                    return;
                }
            }

            // 开始的点是上一个记录的右节点+1，然后分割
            for (int start = right + 1; start <= s.length(); start++) {
                stack.push(s.substring(right, start));
                dfs(right, start, s, stack);
                stack.pop();
            }
        }

        // 是否回文
        private boolean isR(String s) {
            int left = 0;
            int right = s.length() - 1;
            while (left < right) {
                if (s.charAt(left) == s.charAt(right)) {
                    left++;
                    right--;
                } else {
                    return false;
                }
            }
            return true;
        }

    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P131PalindromePartitioning().new Solution();
        System.out.println(solution.partition("aaa"));
        // TO TEST
    }

}